<!DOCTYPE html>
<html lang="zh">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.3.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/yuwanzi.io/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/yuwanzi.io/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/yuwanzi.io/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/yuwanzi.io/images/logo.svg" color="#222">

<link rel="stylesheet" href="/yuwanzi.io/css/main.css">



<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.1/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"suyuhuan.gitee.io","root":"/yuwanzi.io/","images":"/yuwanzi.io/images","scheme":"Muse","version":"8.2.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"Suche...","empty":"We didn't find any results for the search: ${query}","hits_time":"${hits} results found in ${time} ms","hits":"${hits} results found"}};
  </script>
<meta name="description" content="概述 散列表(Hash Table,也叫哈希表),它是根据键而直接访问在内存存储位置的数据结构.也可以说是用一个数组来实现的无序的符号表,将键作为数组的索引而数组中键i处存储的就是它对应的值. 散列表通过散列函数将键转化为数组的索引来访问数组中的键值对. 在散列表的算法中,最重要的两个操作如下.  使用散列函数将被查找的键转化为数组的一个索引.   处理散列表中的碰撞冲突问题.   性质  若关键">
<meta property="og:type" content="article">
<meta property="og:title" content="《Algorithms,4th Edition》读书笔记-散列表">
<meta property="og:url" content="https://suyuhuan.gitee.io/yuwanzi.io/2017/04/13/2017-4-13-hash_table/index.html">
<meta property="og:site_name" content="玉丸子 | Blog">
<meta property="og:description" content="概述 散列表(Hash Table,也叫哈希表),它是根据键而直接访问在内存存储位置的数据结构.也可以说是用一个数组来实现的无序的符号表,将键作为数组的索引而数组中键i处存储的就是它对应的值. 散列表通过散列函数将键转化为数组的索引来访问数组中的键值对. 在散列表的算法中,最重要的两个操作如下.  使用散列函数将被查找的键转化为数组的一个索引.   处理散列表中的碰撞冲突问题.   性质  若关键">
<meta property="og:locale">
<meta property="og:image" content="http://algs4.cs.princeton.edu/34hash/images/hashing-crux.png">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/c36f16f5357aeb5b0fa2fe3040e74282d62f8881">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2b910a452063a4769272110d8d22cab053d433d">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/fa1d43b27a17bf57baf12626ad7cfbf8ee9bb96d">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/c36f16f5357aeb5b0fa2fe3040e74282d62f8881">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/989ebc7db55ece5d29e2a8baa005e876ef486e4e">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/989ebc7db55ece5d29e2a8baa005e876ef486e4e">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc04a0c2f72156976761fa24dd4ba098855b7dca">
<meta property="og:image" content="https://wikimedia.org/api/rest_v1/media/math/render/svg/3aad2b022083cbc8aef0745526f3a448e7d96160">
<meta property="og:image" content="http://algs4.cs.princeton.edu/34hash/images/modular-hashing.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/34hash/images/separate-chaining.png">
<meta property="og:image" content="http://algs4.cs.princeton.edu/34hash/images/linear-probing.png">
<meta property="article:published_time" content="2017-04-13T10:00:00.000Z">
<meta property="article:modified_time" content="2020-11-07T00:58:17.000Z">
<meta property="article:author" content="玉丸子">
<meta property="article:tag" content="2017">
<meta property="article:tag" content="Algorithms">
<meta property="article:tag" content="数据结构">
<meta property="article:tag" content="HashTable">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://algs4.cs.princeton.edu/34hash/images/hashing-crux.png">


<link rel="canonical" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/04/13/2017-4-13-hash_table/">


<script class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh'
  };
</script>
<title>《Algorithms,4th Edition》读书笔记-散列表 | 玉丸子 | Blog</title>
  




  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

<link rel="alternate" href="/yuwanzi.io/atom.xml" title="玉丸子 | Blog" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="Navigationsleiste an/ausschalten" role="button">
    </div>
  </div>

  <div class="site-meta">

    <a href="/yuwanzi.io/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">玉丸子 | Blog</h1>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>







</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          Inhaltsverzeichnis
        </li>
        <li class="sidebar-nav-overview">
          Übersicht
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%A6%82%E8%BF%B0"><span class="nav-number">1.</span> <span class="nav-text">概述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%80%A7%E8%B4%A8"><span class="nav-number">2.</span> <span class="nav-text">性质</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0"><span class="nav-number">3.</span> <span class="nav-text">散列函数</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%AE%9E%E7%8E%B0%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B0%E7%9A%84%E5%87%A0%E7%A7%8D%E6%96%B9%E6%B3%95"><span class="nav-number">3.1.</span> <span class="nav-text">实现散列函数的几种方法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%AD%A3%E6%95%B4%E6%95%B0"><span class="nav-number">3.2.</span> <span class="nav-text">正整数</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%B5%AE%E7%82%B9%E6%95%B0"><span class="nav-number">3.3.</span> <span class="nav-text">浮点数</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">3.4.</span> <span class="nav-text">字符串</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E7%BB%84%E5%90%88%E9%94%AE"><span class="nav-number">3.5.</span> <span class="nav-text">组合键</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Java%E4%B8%AD%E7%9A%84%E7%BA%A6%E5%AE%9A"><span class="nav-number">3.6.</span> <span class="nav-text">Java中的约定</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E8%BD%AF%E7%BC%93%E5%AD%98"><span class="nav-number">3.7.</span> <span class="nav-text">软缓存</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%80%BB%E7%BB%93"><span class="nav-number">3.8.</span> <span class="nav-text">总结</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E4%BA%8E%E6%8B%89%E9%93%BE%E6%B3%95%E7%9A%84%E6%95%A3%E5%88%97%E8%A1%A8"><span class="nav-number">4.</span> <span class="nav-text">基于拉链法的散列表</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E6%9F%A5%E6%89%BE%E3%80%81%E6%8F%92%E5%85%A5%E3%80%81%E5%88%A0%E9%99%A4"><span class="nav-number">4.1.</span> <span class="nav-text">查找、插入、删除</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9F%BA%E4%BA%8E%E7%BA%BF%E6%80%A7%E6%8E%A2%E6%B5%8B%E6%B3%95%E7%9A%84%E6%95%A3%E5%88%97%E8%A1%A8"><span class="nav-number">5.</span> <span class="nav-text">基于线性探测法的散列表</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%88%A0%E9%99%A4"><span class="nav-number">5.1.</span> <span class="nav-text">删除</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E9%94%AE%E7%B0%87"><span class="nav-number">5.2.</span> <span class="nav-text">键簇</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%80%BB%E7%BB%93-1"><span class="nav-number">6.</span> <span class="nav-text">总结</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#end"><span class="nav-number">7.</span> <span class="nav-text">end</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">玉丸子</p>
  <div class="site-description" itemprop="description">这里是玉丸子的个人博客,与你一起发现更大的世界。</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/yuwanzi.io/archives">
          <span class="site-state-item-count">68</span>
          <span class="site-state-item-name">Artikel</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/yuwanzi.io/categories/">
        <span class="site-state-item-count">39</span>
        <span class="site-state-item-name">Kategorien</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/yuwanzi.io/tags/">
        <span class="site-state-item-count">46</span>
        <span class="site-state-item-name">schlagwörter</span></a>
      </div>
  </nav>
</div>



        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh">
    <link itemprop="mainEntityOfPage" href="https://suyuhuan.gitee.io/yuwanzi.io/2017/04/13/2017-4-13-hash_table/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/yuwanzi.io/images/avatar.gif">
      <meta itemprop="name" content="玉丸子">
      <meta itemprop="description" content="这里是玉丸子的个人博客,与你一起发现更大的世界。">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="玉丸子 | Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          《Algorithms,4th Edition》读书笔记-散列表
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">Veröffentlicht am</span>

      <time title="Erstellt: 2017-04-13 18:00:00" itemprop="dateCreated datePublished" datetime="2017-04-13T18:00:00+08:00">2017-04-13</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">Bearbeitet am</span>
        <time title="Geändert am: 2020-11-07 08:58:17" itemprop="dateModified" datetime="2020-11-07T08:58:17+08:00">2020-11-07</time>
      </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">in</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/" itemprop="url" rel="index"><span itemprop="name">Algorithms</span></a>
        </span>
          . 
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a>
        </span>
          . 
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/yuwanzi.io/categories/Algorithms/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/HashTable/" itemprop="url" rel="index"><span itemprop="name">HashTable</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h3 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h3><hr>
<p><code>散列表</code>(<code>Hash Table</code>,也叫<code>哈希表</code>),它是根据键而直接访问在内存存储位置的数据结构.也可以说是用一个数组来实现的<strong>无序的符号表</strong>,将键作为数组的索引而数组中键<code>i</code>处存储的就是它对应的值.</p>
<p><code>散列表</code>通过<code>散列函数</code>将键转化为数组的索引来访问数组中的键值对.</p>
<p>在<code>散列表</code>的算法中,最重要的两个操作如下.</p>
<ol>
<li>使用<code>散列函数</code>将被查找的键转化为数组的一个索引.</li>
</ol>
<ol start="2">
<li>处理散列表中的<code>碰撞冲突</code>问题.</li>
</ol>
<p><img src="http://algs4.cs.princeton.edu/34hash/images/hashing-crux.png"></p>
<h3 id="性质"><a href="#性质" class="headerlink" title="性质"></a>性质</h3><hr>
<ul>
<li>若关键字为<code>k</code>,则其值存放于<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c36f16f5357aeb5b0fa2fe3040e74282d62f8881">的存储位置上.由此,不需要比较便可直接取得所查记录.称这个对应关系<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61">为<code>散列函数</code>,按照这个思想建立的符合表为<code>散列表</code>.</li>
</ul>
<ul>
<li>对不同的键可能会得到同一个<code>散列地址</code>,即<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2b910a452063a4769272110d8d22cab053d433d">,而<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fa1d43b27a17bf57baf12626ad7cfbf8ee9bb96d">,这种现象被称为<code>碰撞冲突</code>.具有相同函数值的键对该<code>散列函数</code>来说称做同义词.综上所述,根据散列函数<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c36f16f5357aeb5b0fa2fe3040e74282d62f8881">和处理<code>碰撞冲突</code>的方法将一组键映射到一个有限的连续的地址集(区间)上,这种表称为<code>散列表</code>,这一映射过程称为<code>散列</code>,所得的存储位置称为<code>散列地址</code>.</li>
</ul>
<ul>
<li>若对于键集合中的任一个键,经<code>散列函数</code>映射到地址集合中任何一个地址的概率是相等的,则这个<code>散列函数</code>被称为<code>均匀散列函数</code>,它可以减少<code>碰撞冲突</code>.</li>
</ul>
<h3 id="散列函数"><a href="#散列函数" class="headerlink" title="散列函数"></a>散列函数</h3><hr>
<p><code>散列函数</code>用于将键转化为数组的索引.如果我们有一个能够保存M个键值对的数组,那么我们就需要一个能够将任意键转化为该数组范围内的索引([0,M-1]范围内的整数)的<code>散列函数</code></p>
<p><code>散列函数</code>与键的类型有关,对于每种类型的键都需要一个与之对应的<code>散列函数</code>.</p>
<h4 id="实现散列函数的几种方法"><a href="#实现散列函数的几种方法" class="headerlink" title="实现散列函数的几种方法"></a>实现散列函数的几种方法</h4><ul>
<li>直接定址法 : 取<code>key</code>或者<code>key</code>的某个线性函数值为<code>散列地址</code>.即<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/989ebc7db55ece5d29e2a8baa005e876ef486e4e">或<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/989ebc7db55ece5d29e2a8baa005e876ef486e4e">其中a,b为常数(这种<code>散列函数</code>叫做自身函数).</li>
</ul>
<ul>
<li>数字分析法 : 假设<code>key</code>是以<code>r</code>为基的数,并且<code>散列表</code>中可能出现的<code>key</code>都是事先知道的,则可取<code>key</code>的若干数位组成<code>散列地址</code>.</li>
</ul>
<ul>
<li>平方取中法 : 取<code>key</code>平方后的中间几位为<code>散列地址</code>.通常在选定<code>散列函数</code>时不一定能知道<code>key</code>的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的<code>key</code>得到的<code>散列地址</code>也是随机的.取的位数由表长决定.</li>
</ul>
<ul>
<li>折叠法 : 将<code>key</code>分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为<code>散列地址</code>.</li>
</ul>
<ul>
<li>除留余数法 : 取<code>key</code>被某个不大于<code>散列表</code>长度<code>m</code>的数<code>p</code>除后所得的余数为<code>散列地址</code>.即<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bc04a0c2f72156976761fa24dd4ba098855b7dca">,<img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3aad2b022083cbc8aef0745526f3a448e7d96160">.不仅可以对<code>key</code>直接取模，也可在<code>折叠法</code>、<code>平方取中法</code>等运算之后取模。对<code>p</code>的选择很重要，一般取<code>素数</code>或<code>m</code>，若<code>p</code>选择不好，容易产生<code>碰撞冲突</code>.</li>
</ul>
<h4 id="正整数"><a href="#正整数" class="headerlink" title="正整数"></a>正整数</h4><p>将正整数<code>散列</code>一般使用的是<code>除留余数法</code>.我们选择大小为<strong>素数</strong><code>M</code>的数组,对于任意正整数<code>k</code>,计算<code>k</code>除以<code>M</code>的余数(即<code>k%M</code>).它能够有效地将<code>key</code>散布在0到M-1的范围内.</p>
<p>如果<code>M</code>不是<strong>素数</strong>,可能无法利用<code>key</code>中包含的所有信息,这<strong>可能导致无法均匀地散列散列值</strong>.</p>
<p><img src="http://algs4.cs.princeton.edu/34hash/images/modular-hashing.png"></p>
<h4 id="浮点数"><a href="#浮点数" class="headerlink" title="浮点数"></a>浮点数</h4><p>对浮点数进行散列一般是将<code>key</code>表示为二进制数然后再使用<code>除留余数法</code>.</p>
<h4 id="字符串"><a href="#字符串" class="headerlink" title="字符串"></a>字符串</h4><p><code>除留余数法</code>也可以处理较长的<code>key</code>,例如字符串,我们只需将它们当成大整数即可.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> hash = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s.length(); i++) &#123;</span><br><span class="line">   	hash = (R * hash + s.charAt(i)) % M;</span><br><span class="line">&#125;	</span><br></pre></td></tr></table></figure>
<p>Java的<code>charAt()</code>函数能够返回一个char值,即一个非负16位整数.如果<code>R</code>比任何字符的值都大,这种计算相当于将字符串当作一个N位的<code>R</code>进制值,将它除以<code>M</code>并取余.只要<code>R</code>足够小,不造成溢出,那么结果就能够落在0至M-1之间.可以使用一个较小的素数,例如31.</p>
<h4 id="组合键"><a href="#组合键" class="headerlink" title="组合键"></a>组合键</h4><p>如果<code>key</code>的类型含有多个整型变量,我们可以和字符串类型一样将它们混合起来.</p>
<p>例如,<code>key</code>的类型为Date,其中含有几个整型的域 : day(两个数字表示的日),month(两个数字表示的月),year(四个数字表示的年).我们可以这样计算它的散列值: </p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> hash = (((day * R + month) % M) * R + year) % M; </span><br></pre></td></tr></table></figure>
<h4 id="Java中的约定"><a href="#Java中的约定" class="headerlink" title="Java中的约定"></a>Java中的约定</h4><p>在Java中如果要为自定义的数据类型定义散列函数,需要同时重写<code>hashCode()</code>和<code>equals()</code>两个函数,并要遵守以下规则.</p>
<ul>
<li><code>hashCode()</code>与<code>equals()</code>的结果必须保持一致性.即<code>a.equals(b)</code>返回true,则<code>a.hashCode()</code>的返回值也必然和<code>b.hashCode()</code>的返回值相同.</li>
</ul>
<ul>
<li>但如果两个对象的<code>hashCode()</code>函数的返回值相同,这两个对象也有可能不同,还需要用<code>equals()</code>函数进行判断.</li>
</ul>
<p>一个使用<code>除留余数法</code>的简单<code>散列函数</code>如下,它会将符号位屏蔽(将一个32位整数变为一个31位非负整数).</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Key key)</span> </span>&#123;</span><br><span class="line">   <span class="keyword">return</span> (key.hashCode() &amp; <span class="number">0x7fffffff</span>) % M;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="软缓存"><a href="#软缓存" class="headerlink" title="软缓存"></a>软缓存</h4><p>由于<code>散列函数</code>的计算有可能会很耗时,我们可以进行缓存优化,将每个<code>key</code>的散列值缓存起来(可以在每个<code>key</code>中使用一个hash变量来保存它的<code>hashCode()</code>的返回值).</p>
<p>当第一次调用<code>hashCode()</code>时,需要计算对象的散列值,但之后对<code>hashCode()</code>方法的调用会直接返回hash变量的值.</p>
<h4 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h4><p>总之,要想实现一个优秀的<code>散列函数</code>需要满足以下的条件.</p>
<ol>
<li>一致性,等价的<code>key</code>必然产生相等的散列值.</li>
</ol>
<ol start="2">
<li>.高效性,计算简便.</li>
</ol>
<ol start="3">
<li>均匀性,均匀地散列所有的<code>key</code>.</li>
</ol>
<h3 id="基于拉链法的散列表"><a href="#基于拉链法的散列表" class="headerlink" title="基于拉链法的散列表"></a>基于拉链法的散列表</h3><hr>
<p>拉链法是解决<code>碰撞冲突</code>的一种策略,它的核心思想是 : 将大小为<code>M</code>的<strong>数组中的每个元素指向一条链表</strong>,链表中的每个节点都存储了散列值为该元素的索引的键值对.</p>
<p>拉链法的实现一般分为以下两种: </p>
<ol>
<li>使用一个原始的链表数据类型来表示数组中的每个元素.</li>
</ol>
<ol start="2">
<li>使用一个符号表实现来表示数组中的每个元素(这个方法实现简单但效率偏低).</li>
</ol>
<p><img src="http://algs4.cs.princeton.edu/34hash/images/separate-chaining.png"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">SeparateChainingHashST</span>&lt;<span class="title">K</span>, <span class="title">V</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> INIT_CAPACITY = <span class="number">4</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> n; <span class="comment">// the number of key-value pairs in the symbol table</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> m; <span class="comment">// the number of size of separate chaining table</span></span><br><span class="line">    <span class="keyword">private</span> Node&lt;K, V&gt;[] table; <span class="comment">// array of linked-list symbol tables</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">K</span>, <span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">        <span class="keyword">private</span> K key;</span><br><span class="line">        <span class="keyword">private</span> V value;</span><br><span class="line">        <span class="keyword">private</span> Node&lt;K,V&gt; next;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(K key, V value, Node next)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.key = key;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">            <span class="keyword">this</span>.next = next;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">	<span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> ((key.hashCode()) &amp; <span class="number">0x7fffffff</span>) % m;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;	</span><br></pre></td></tr></table></figure>
<h4 id="查找、插入、删除"><a href="#查找、插入、删除" class="headerlink" title="查找、插入、删除"></a>查找、插入、删除</h4><p>基于拉链法的<code>散列表</code>的查找、插入、删除算法基本分为两步:</p>
<ol>
<li>首先根据散列值找到对应的链表.</li>
</ol>
<ol start="2">
<li>然后沿着这条链表进行相应的操作.</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called get() with key is null.&quot;</span>);</span><br><span class="line">    <span class="keyword">int</span> i = hash(key);</span><br><span class="line">    Node x = table[i];</span><br><span class="line">    <span class="keyword">while</span> (x != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (key.equals(x.key))</span><br><span class="line">            <span class="keyword">return</span> (V) x.value;</span><br><span class="line">        x = x.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br><span class="line">	</span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called put() with key is null.&quot;</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (value == <span class="keyword">null</span>) &#123;</span><br><span class="line">        remove(key);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// double table size if average length of list &gt;= 10</span></span><br><span class="line">    <span class="keyword">if</span> (n &gt;= <span class="number">10</span> * m)</span><br><span class="line">        resize(<span class="number">2</span> * m);</span><br><span class="line">    <span class="keyword">int</span> i = hash(key);</span><br><span class="line">    Node x = table[i];</span><br><span class="line">    Node p = <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">while</span> (x != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (key.equals(x.key)) &#123;</span><br><span class="line">            x.value = value;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        p = x;</span><br><span class="line">        x = x.next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (p == <span class="keyword">null</span>) &#123;</span><br><span class="line">        table[i] = <span class="keyword">new</span> Node(key, value, <span class="keyword">null</span>);</span><br><span class="line">        n++;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        p.next = <span class="keyword">new</span> Node(key, value, <span class="keyword">null</span>);</span><br><span class="line">        n++;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">	</span><br><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">remove</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called remove() with key is null.&quot;</span>);</span><br><span class="line">    <span class="keyword">if</span> (isEmpty())</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;called remove() with empty symbol table.&quot;</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (!contains(key))</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">int</span> i = hash(key);</span><br><span class="line">    Node x = table[i];</span><br><span class="line">    Node p = <span class="keyword">null</span>;</span><br><span class="line">    V oldValue = <span class="keyword">null</span>;</span><br><span class="line">    <span class="keyword">while</span> (x != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (key.equals(x.key)) &#123;</span><br><span class="line">            oldValue = (V) x.value;</span><br><span class="line">            <span class="keyword">if</span> (p == <span class="keyword">null</span>) &#123;</span><br><span class="line">                table[i] = x.next;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                p.next = x.next;</span><br><span class="line">            &#125;</span><br><span class="line">            n--;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        p = x;</span><br><span class="line">        x = x.next;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// halve table size if average length of list &lt;= 2</span></span><br><span class="line">    <span class="keyword">if</span> (m &gt; INIT_CAPACITY &amp;&amp; n &lt;= <span class="number">2</span> * m)</span><br><span class="line">        resize(m / <span class="number">2</span>);</span><br><span class="line">    <span class="keyword">return</span> oldValue;</span><br><span class="line">&#125;	</span><br></pre></td></tr></table></figure>
<h3 id="基于线性探测法的散列表"><a href="#基于线性探测法的散列表" class="headerlink" title="基于线性探测法的散列表"></a>基于线性探测法的散列表</h3><hr>
<p>解决<code>碰撞冲突</code>的另一种策略是使用线性探测法.它的核心思想是: 使用大小为<code>M</code>的数组保存<code>N</code>个键值对,其中<code>M&gt;N</code>.这种方法<strong>需要依靠数组中的空位来解决<code>碰撞冲突</code></strong>,基于这种策略的所有方法被统称为<code>开放地址散列表</code>.</p>
<p><code>开放地址散列表</code>中最简单的方法就是线性探测法: 当发生<code>碰撞冲突</code>时,我们直接检查<code>散列表</code>中的下一个位置(将索引值加1).它可能会产生三种结果: </p>
<ol>
<li>命中,该位置的<code>key</code>和被查找的<code>key</code>相同.</li>
</ol>
<ol start="2">
<li>未命中,<code>key</code>为空(该位置没有<code>key</code>).</li>
</ol>
<ol start="3">
<li>继续查找,该位置的<code>key</code>和被查找的<code>key</code>不同.</li>
</ol>
<p>我们使用<code>散列函数</code>找到<code>key</code>在数组中的索引,检查其中的<code>key</code>和被查找的<code>key</code>是否相同.如果不同则继续查找(将索引值加1,到达数组结尾时折回数组的开头),直到找到该<code>key</code>或者遇到一个空元素.</p>
<p><code>开放地址散列表</code>的核心思想是: 与其将内存用作链表,不如将它们作为在<code>散列表</code>的空元素(这些空元素可以作为查找结束的标识).</p>
<p><img src="http://algs4.cs.princeton.edu/34hash/images/linear-probing.png"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinearProbingHashST</span>&lt;<span class="title">K</span>, <span class="title">V</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> INIT_CAPACITY = <span class="number">4</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> n; <span class="comment">// the number of key-value pairs in the symbol table</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> m; <span class="comment">// the number of size of linear probing table</span></span><br><span class="line">    <span class="keyword">private</span> K[] keys; <span class="comment">// the keys</span></span><br><span class="line">    <span class="keyword">private</span> V[] vals; <span class="comment">// the values</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Initializes an empty symbol table.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LinearProbingHashST</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>(INIT_CAPACITY);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Initializes an empty symbol table with the specified initial capacity.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> capacity the initial capacity</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LinearProbingHashST</span><span class="params">(<span class="keyword">int</span> capacity)</span> </span>&#123;</span><br><span class="line">        m = capacity;</span><br><span class="line">        n = <span class="number">0</span>;</span><br><span class="line">        keys = (K[]) <span class="keyword">new</span> Object[m];</span><br><span class="line">        vals = (V[]) <span class="keyword">new</span> Object[m];</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called get() with key is null.&quot;</span>);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = hash(key); keys[i] != <span class="keyword">null</span>; i = (i + <span class="number">1</span>) % m) &#123;</span><br><span class="line">            <span class="keyword">if</span> (keys[i].equals(key))</span><br><span class="line">                <span class="keyword">return</span> vals[i];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called put() with key is null.&quot;</span>);</span><br><span class="line">        <span class="keyword">if</span> (value == <span class="keyword">null</span>) &#123;</span><br><span class="line">            delete(key);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// double table size if 50% full</span></span><br><span class="line">        <span class="keyword">if</span> (n &gt;= m / <span class="number">2</span>) resize(<span class="number">2</span> * m);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> i;</span><br><span class="line">        <span class="keyword">for</span> (i = hash(key); keys[i] != <span class="keyword">null</span>; i = (i + <span class="number">1</span>) % m) &#123;</span><br><span class="line">            <span class="keyword">if</span> (keys[i].equals(key)) &#123;</span><br><span class="line">                vals[i] = value;</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        keys[i] = key;</span><br><span class="line">        vals[i] = value;</span><br><span class="line">        n++;</span><br><span class="line">    &#125;	</span><br><span class="line">&#125;	</span><br></pre></td></tr></table></figure>
<h4 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h4><p>基于线性探测法的<code>散列表</code>的删除操作较为复杂,我们不能直接将<code>key</code>所在的位置设为<code>null</code>,这样会使在此位置之后的元素无法被查找到.</p>
<p>因此,我们需要<strong>将被删除键的右侧的所有键重新插入到<code>散列表</code>中</strong>.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">delete</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;called delete() with key is null.&quot;</span>);</span><br><span class="line">    <span class="keyword">if</span> (isEmpty())</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;called delete() with empty symbol table.&quot;</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (!contains(key))</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">// find position i of key</span></span><br><span class="line">    <span class="keyword">int</span> i = hash(key);</span><br><span class="line">    <span class="keyword">while</span> (!key.equals(keys[i])) &#123;</span><br><span class="line">        i = (i + <span class="number">1</span>) % m;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    V oldValue = vals[i];</span><br><span class="line">    <span class="comment">// delete key and associated value</span></span><br><span class="line">    keys[i] = <span class="keyword">null</span>;</span><br><span class="line">    vals[i] = <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// rehash all keys in same cluster</span></span><br><span class="line">    i = (i + <span class="number">1</span>) % m;</span><br><span class="line">    <span class="keyword">while</span> (keys[i] != <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="comment">// delete keys[i] an vals[i] and reinsert</span></span><br><span class="line">        K keyToRehash = keys[i];</span><br><span class="line">        V valToRehash = vals[i];</span><br><span class="line">        keys[i] = <span class="keyword">null</span>;</span><br><span class="line">        vals[i] = <span class="keyword">null</span>;</span><br><span class="line">        n--;</span><br><span class="line">        put(keyToRehash, valToRehash);</span><br><span class="line">        i = (i + <span class="number">1</span>) % m;</span><br><span class="line">    &#125;</span><br><span class="line">    n--;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// halves size of array if it&#x27;s 12.5% full or less</span></span><br><span class="line">    <span class="keyword">if</span> (n &gt; <span class="number">0</span> &amp;&amp; n &lt;= m / <span class="number">8</span>) resize(m / <span class="number">2</span>);</span><br><span class="line">    <span class="function"><span class="keyword">assert</span> <span class="title">check</span><span class="params">()</span></span>;</span><br><span class="line">    <span class="keyword">return</span> oldValue;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="键簇"><a href="#键簇" class="headerlink" title="键簇"></a>键簇</h4><p>线性探测法的平均成本取决于元素在插入数组后聚集成的一组连续的条目,也叫作<code>键簇</code>.</p>
<p>显然,短小的<code>键簇</code>才能保证较高的效率.随着插入的<code>key</code>越来越多,这个要求会很难满足,较长的<code>键簇</code>会越来越多.<code>长键簇</code>的可能性要比<code>短键簇</code>更大,因为新键的散列值无论落在<code>键簇</code>的任何位置都会使它的长度加1.</p>
<h3 id="总结-1"><a href="#总结-1" class="headerlink" title="总结"></a>总结</h3><hr>
<p><code>散列表</code>使用了适度的空间和时间并在这两个极端之间找到了一种平衡,所以它可以在一般应用中实现拥有(均摊后)常数级别的查找和插入操作的<code>符号表</code>.</p>
<p>但<code>散列表</code>是很难实现有序操作的,这是因为散列最主要的目的在于均匀地将键散布开来,因此在计算散列后键的顺序信息就已经丢失了.</p>
<p>同时,<code>散列表</code>的性能也依赖于<code>α=N/M</code>的比值,其中<code>α</code>称为<code>散列表</code>的使用率.对于<code>拉链法</code>来说,<code>α</code>是每条链表的长度,因此一般大于1.对于<code>线性探测法</code>来说,<code>α</code>是表中已被占用的空间的比例,它是不可能大于1的.</p>
<p><code>散列表</code>的性能虽然高效,但它也有以下的局限性: </p>
<ul>
<li>每种类型的键都需要一个优秀的<code>散列函数</code>.</li>
</ul>
<ul>
<li>性能保证来自于<code>散列函数</code>的质量.</li>
</ul>
<ul>
<li><code>散列函数</code>的计算可能复杂而且昂贵.</li>
</ul>
<ul>
<li>难以支持有序性相关的操作.</li>
</ul>
<h3 id="end"><a href="#end" class="headerlink" title="end"></a>end</h3><hr>
<ul>
<li>Author : <a target="_blank" rel="noopener" href="https://github.com/SylvanasSun">SylvanasSun</a></li>
</ul>
<ul>
<li>Email : <a href="mailto:&#115;&#121;&#108;&#x76;&#97;&#110;&#97;&#115;&#x73;&#117;&#x6e;&#x5f;&#120;&#x74;&#122;&#x40;&#x31;&#54;&#x33;&#46;&#x63;&#111;&#109;">&#115;&#121;&#108;&#x76;&#97;&#110;&#97;&#115;&#x73;&#117;&#x6e;&#x5f;&#120;&#x74;&#122;&#x40;&#x31;&#54;&#x33;&#46;&#x63;&#111;&#109;</a></li>
</ul>
<ul>
<li>文中的完整实现代码见我的<a target="_blank" rel="noopener" href="https://github.com/SylvanasSun/algs4-study">GitHub</a> &amp; <a target="_blank" rel="noopener" href="https://gist.github.com/SylvanasSun/6872abd0fad061de28466cb775a84cea">Gist</a></li>
</ul>
<ul>
<li>文中参考资料引用自<a target="_blank" rel="noopener" href="http://algs4.cs.princeton.edu/34hash/">&lt;&lt;Algorithms,4th Edition&gt;&gt;</a> &amp; <a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Hash_table">Wikepedia</a></li>
</ul>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/yuwanzi.io/tags/2017/" rel="tag"># 2017</a>
              <a href="/yuwanzi.io/tags/Algorithms/" rel="tag"># Algorithms</a>
              <a href="/yuwanzi.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"># 数据结构</a>
              <a href="/yuwanzi.io/tags/HashTable/" rel="tag"># HashTable</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/04/08/2017-4-08-avl_tree/" rel="prev" title="平衡查找树之AVL树">
                  <i class="fa fa-chevron-left"></i> 平衡查找树之AVL树
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/yuwanzi.io/2017/05/29/2017-5-29-cas_concurrent_stack/" rel="next" title="谈谈如何实现一个非阻塞的线程安全的集合">
                  谈谈如何实现一个非阻塞的线程安全的集合 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>







<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">玉丸子</span>
</div>
  <div class="powered-by">Erstellt mit  <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a>
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js"></script>
<script src="/yuwanzi.io/js/utils.js"></script><script src="/yuwanzi.io/js/motion.js"></script><script src="/yuwanzi.io/js/schemes/muse.js"></script><script src="/yuwanzi.io/js/next-boot.js"></script>

  






  





</body>
</html>
